package lcaDeepestLeaves;

import java.util.*;
class Solution {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        Map<TreeNode,int[]>map = new HashMap<>();
        dfs(root,map);
        TreeNode p = root;
        while (p!=null) {
            int[] h = map.get(p);
            if(h[0]>h[1]) {
                p = p.left;
            } else if (h[0]<h[1]) {
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }
    private int dfs (TreeNode root,Map<TreeNode,int[]>map){
        if(root == null) {
            return 0;
        }
        int lh = dfs(root.left,map); // 左子树的高度
        int rh = dfs(root.right,map); // 右子树的高度
        map.put(root,new int[]{lh,rh});
        return Math.max(lh+1,rh+1);
    }
}
